Матч 323, Несводимое число (IrreducibleNumber)

Дивизион 2, Уровень 1

Задан массив чисел a. Число k называется несводимым, если его нельзя представить в виде суммы одного или более элементов из a. Найти наименьшее положительное несводимое число.

Класс: IrreducibleNumber

Метод: int getIrreducible(vector<int> a)

Ограничения: a содержит от 1 до 3 элементов, 1 £ a[i] £ 100.

Вход. Массив чисел a.

Выход. Наименьшее положительное несводимое число.

Пример входа

a

{1, 1}

{1, 2}

{4, 1, 3}

Пример выхода

3

4

2

РЕШЕНИЕ

элементарные вычисления

Отсортируем элементы массива a. Пусть c_k = . Если c_k + 1 < a_k+1, то число c_k + 1 не представимо в виде суммы элементов массива a. Если для всех k (0 £ k < n) выполняется неравенство c_k + 1 < a_k+1, то искомым числом будет c_n + 1, где n – размер массива a.

ПРОГРАММА

#include <cstdio>

#include <algorithm>

#include <vector>

using namespace std;

class IrreducibleNumber

{

public:

int getIrreducible(vector<int> a)

{

int i, c = 0;

sort(a.begin(),a.end());

for(i = 0; i < a.size(); i++)

{

if (c + 1 < a[i]) return c + 1;

c += a[i];

}

return c + 1;

}

};